package com.hy.greedy;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class MergeSpace {


    /**
     * 56. 合并区间
     * 力扣题目链接
     *
     * 给出一个区间的集合，请合并所有重叠的区间。
     *
     * 示例 1:
     *
     * 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出: [[1,6],[8,10],[15,18]]
     * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     *
     * 思路
     * 大家应该都感觉到了，此题一定要排序，那么按照左边界排序，还是右边界排序呢？
     *
     * 都可以！
     *
     * 那么我按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。
     *
     * 局部最优可以推出全局最优，找不出反例，试试贪心。
     *
     * 那有同学问了，本来不就应该合并最大右边界么，这和贪心有啥关系？
     *
     * 有时候贪心就是常识！哈哈
     *
     *
     * @param num
     * @return
     */
    public int[][] mergeSpace(int [][] num){
        List<int[]> res = new LinkedList<>();
        Arrays.sort(num,(a,b)-> {
            return a[0] - b[0];
        });
        int left = num[0][0];
        int right = num[0][1];
        for (int i = 1; i < num.length; i++) {
            //如果左边界大于最大右边界
            if (num[i][0] > right){
                //加入区间 并且更新start
                res.add(new int[]{left,right});
                left = num[i][0];
                right = num[i][1];
            }else {
                //更新最大右边界
                right = Math.max(right,num[i][1]);
            }
        }
        res.add(new int[]{left,right});
        return res.toArray(new int[res.size()][]);
    }

    public static void main(String[] args) {
        int [][] num = {{1,3},{2,6},{8,10},{15,18}};
        MergeSpace mergeSpace = new MergeSpace();
        System.out.println("res: "+Arrays.deepToString(mergeSpace.mergeSpace(num)));
    }
}
